package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

/**
 * Created with IntelliJ IDEA.
 * tree
 * 99. 恢复二叉搜索树
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/24 21:07
 */
public class RecoverTree {

    public static void main(String[] args) {
        RecoverTree test = new RecoverTree();

        TreeNode instance14 = TreeNode.getInstance14();

        System.out.println(instance14);
        test.recoverTree(instance14);
        System.out.println(instance14);

    }

    private long a = Long.MAX_VALUE;
    private long b = Long.MAX_VALUE;
    private long c = Long.MAX_VALUE;
    private long d = Long.MAX_VALUE;
    private long last = Long.MIN_VALUE;

    public void recoverTree(TreeNode root) {
        find(root);
        if (c == Long.MAX_VALUE) {
            c = b;
            d = a;
        } else {
            b = d;
            c = d;
            d = a;
        }
        change(root);
    }

    private void change(TreeNode node) {
        if (node == null) {
            return;
        }
        change(node.left);
        if (node.val == a) {
            node.val = (int) b;
        } else if (node.val == c) {
            node.val = (int) d;
            return;
        }
        change(node.right);
    }

    private void find(TreeNode node) {
        if (node == null) {
            return;
        }
        find(node.left);
        int val = node.val;
        if (val <= last) {
            if (a == Long.MAX_VALUE) {
                a = last;
                b = val;
            } else {
                c = last;
                d = val;
                return;
            }
        }
        last = val;
        find(node.right);
    }

}
